#include <vector>
#include <iostream>

using namespace std;

struct ListNode
{
    int val;
    ListNode * next;
    ListNode() : val(0), next(nullptr)
    {}
    ListNode(int val) : val(val), next(nullptr)
    {}
    ListNode(int val, ListNode * next) : val(val), next(next)
    {}
};

class Solution 
{
public:
    ListNode *detectCycle(ListNode *head) 
    {
        if(head == nullptr || head->next == nullptr)
        {
            return nullptr;
        }
        ListNode * slow = head;
        ListNode * fast = head;
        bool flag = false;
        while(fast != nullptr && fast->next != nullptr)
        {
            slow = slow->next;
            fast = fast->next->next;
            if(fast == slow)
            {
                flag = true;
                break;
            }
        }
        if(!flag)
        {
            return nullptr;
        }

        fast = head;
        while(fast != slow)
        {
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }
};

// 辅助函数：创建链表
ListNode* createList(vector<int>& nums) {
    if (nums.empty()) return nullptr;
    
    ListNode* head = new ListNode(nums[0]);
    ListNode* cur = head;
    
    for (int i = 1; i < nums.size(); i++) {
        cur->next = new ListNode(nums[i]);
        cur = cur->next;
    }
    
    return head;
}

// 辅助函数：创建环形链表
ListNode* createCycleList(vector<int>& nums, int pos) {
    if (nums.empty()) return nullptr;
    
    ListNode* head = createList(nums);
    
    if (pos == -1) return head; // 无环
    
    // 找到环的起始位置
    ListNode* cycleStart = head;
    for (int i = 0; i < pos; i++) {
        cycleStart = cycleStart->next;
    }
    
    // 找到链表尾部并连接到环的起始位置
    ListNode* tail = head;
    while (tail->next != nullptr) {
        tail = tail->next;
    }
    tail->next = cycleStart;
    
    return head;
}

// 辅助函数：打印链表信息
void printList(vector<int>& nums, int pos) {
    cout << "链表: [";
    for (int i = 0; i < nums.size(); i++) {
        cout << nums[i];
        if (i < nums.size() - 1) cout << ",";
    }
    cout << "], pos = " << pos;
}

// 辅助函数：获取节点在链表中的位置（仅用于验证结果）
int getNodePosition(ListNode* head, ListNode* target) {
    if (target == nullptr) return -1;
    
    ListNode* cur = head;
    int pos = 0;
    while (cur != nullptr) {
        if (cur == target) return pos;
        cur = cur->next;
        pos++;
        // 防止无限循环
        if (pos > 10000) break;
    }
    return -1;
}

// 辅助函数：释放无环链表内存
void deleteList(ListNode* head) {
    while (head != nullptr) {
        ListNode* temp = head;
        head = head->next;
        delete temp;
    }
}

int main() {
    Solution solution;
    
    // 测试案例1：有环链表 [3,2,0,-4], pos = 1
    cout << "测试案例1: ";
    vector<int> nums1 = {3, 2, 0, -4};
    int pos1 = 1;
    printList(nums1, pos1);
    ListNode* head1 = createCycleList(nums1, pos1);
    ListNode* result1 = solution.detectCycle(head1);
    int resultPos1 = getNodePosition(head1, result1);
    cout << " -> 返回位置: " << resultPos1 << " (期望: 1)" << endl;
    // 注意：有环链表不能用常规方法释放内存
    
    // 测试案例2：有环链表 [1,2], pos = 0
    cout << "测试案例2: ";
    vector<int> nums2 = {1, 2};
    int pos2 = 0;
    printList(nums2, pos2);
    ListNode* head2 = createCycleList(nums2, pos2);
    ListNode* result2 = solution.detectCycle(head2);
    int resultPos2 = getNodePosition(head2, result2);
    cout << " -> 返回位置: " << resultPos2 << " (期望: 0)" << endl;
    
    // 测试案例3：无环链表 [1], pos = -1
    cout << "测试案例3: ";
    vector<int> nums3 = {1};
    int pos3 = -1;
    printList(nums3, pos3);
    ListNode* head3 = createCycleList(nums3, pos3);
    ListNode* result3 = solution.detectCycle(head3);
    cout << " -> 返回: " << (result3 ? "非空节点" : "nullptr") << " (期望: nullptr)" << endl;
    deleteList(head3);
    
    // 测试案例4：空链表
    cout << "测试案例4: ";
    cout << "链表: [], pos = -1";
    ListNode* head4 = nullptr;
    ListNode* result4 = solution.detectCycle(head4);
    cout << " -> 返回: " << (result4 ? "非空节点" : "nullptr") << " (期望: nullptr)" << endl;
    
    // 测试案例5：无环链表 [1,2,3,4], pos = -1
    cout << "测试案例5: ";
    vector<int> nums5 = {1, 2, 3, 4};
    int pos5 = -1;
    printList(nums5, pos5);
    ListNode* head5 = createCycleList(nums5, pos5);
    ListNode* result5 = solution.detectCycle(head5);
    cout << " -> 返回: " << (result5 ? "非空节点" : "nullptr") << " (期望: nullptr)" << endl;
    deleteList(head5);
    
    // 测试案例6：单节点自环 [1], pos = 0
    cout << "测试案例6: ";
    vector<int> nums6 = {1};
    int pos6 = 0;
    printList(nums6, pos6);
    ListNode* head6 = createCycleList(nums6, pos6);
    ListNode* result6 = solution.detectCycle(head6);
    int resultPos6 = getNodePosition(head6, result6);
    cout << " -> 返回位置: " << resultPos6 << " (期望: 0)" << endl;
    
    // 测试案例7：长链表有环 [1,2,3,4,5,6], pos = 2
    cout << "测试案例7: ";
    vector<int> nums7 = {1, 2, 3, 4, 5, 6};
    int pos7 = 2;
    printList(nums7, pos7);
    ListNode* head7 = createCycleList(nums7, pos7);
    ListNode* result7 = solution.detectCycle(head7);
    int resultPos7 = getNodePosition(head7, result7);
    cout << " -> 返回位置: " << resultPos7 << " (期望: 2)" << endl;
    
    return 0;
}